SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Berger code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Berger code</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Telecommunication" class="mw-redirect" title="Telecommunication">telecommunication</a>, a <b>Berger code</b> is a unidirectional <a href="Error_detection_and_correction" title="Error detection and correction">error detecting code</a>, named after its inventor, J. M. Berger. Berger codes can detect all unidirectional errors. Unidirectional errors are errors that only flip ones into zeroes or only zeroes into ones, such as in asymmetric channels. The <a href="Check_bits" class="mw-redirect" title="Check bits">check bits</a> of Berger codes are computed by counting all the zeroes in the information word, and expressing that number in natural binary. If the information word consists of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> bits, then the Berger code needs <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=\lceil \log _{2}(n+1)\rceil }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=\lceil \log _{2}(n+1)\rceil }</annotation>

</semantics>

</math></span><img src="./839c0b08022d776497882591192b84a92aa31688.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.607ex; height:2.843ex;" alt="{\displaystyle k=\lceil \log _{2}(n+1)\rceil }" loading="lazy"></span> "check bits", giving a Berger code of length k+n. (In other words, the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> check bits are enough to check up to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{k}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k}-1}</annotation>

</semantics>

</math></span><img src="./a1f759b5772feacbd43d833f21bafe8a7a15e2ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.747ex; height:2.843ex;" alt="{\displaystyle n=2^{k}-1}" loading="lazy"></span> information bits).

Berger codes can detect any number of one-to-zero bit-flip errors, as long as no zero-to-one errors occurred in the same code word.

Similarly, Berger codes can detect any number of zero-to-one bit-flip errors, as long as no one-to-zero bit-flip errors occur in the same code word.

Berger codes cannot correct any error.

</p><p>Like all unidirectional error detecting codes,

Berger codes can also be used in <a href="Delay-insensitive" class="mw-redirect" title="Delay-insensitive">delay-insensitive</a> circuits.

</p>

<div class="mw-heading mw-heading2"><h2 id="Unidirectional_error_detection">Unidirectional error detection</h2></div>

<p>As stated above, Berger codes detect <i>any</i> number of unidirectional errors. For a <i>given code word</i>, if the only errors that have occurred are that some (or all) bits with value 1 have changed to value 0, then this transformation will be detected by the Berger code implementation. To understand why, consider that there are three such cases:

</p>

<ol><li>Some 1s bit in the information part of the code word have changed to 0s.</li>

<li>Some 1s bits in the check (or <i>redundant</i>) portion of the code word have changed to 0s.</li>

<li>Some 1s bits in both the information and check portions have changed to 0s.</li></ol>

<p>For case 1, the number of 0-valued bits in the information section will, by definition of the error, increase. Therefore, our Berger check code will be lower than the actual 0-bit-count for the data, and so the check will fail.

</p><p>For case 2, the number of 0-valued bits in the information section have stayed the same, but the value of the check data has changed. Since we know some 1s turned into 0s, but no 0s have turned into 1s (that's how we defined the error model in this case), the encoded binary value of the check data will go down (e.g., from binary 1011 to 1010, or to 1001, or 0011). Since the information data has stayed the same, it has the same number of zeros it did before, and that will no longer match the mutated check value.

</p><p>For case 3, where bits have changed in both the information and the check sections, notice that the number of zeros in the information section has <i>gone up</i>, as described for case 1, and the binary value stored in the check portion has <i>gone down</i>, as described for case 2. Therefore, there is no chance that the two will end up mutating in such a way as to become a different valid code word.

</p><p>A similar analysis can be performed, and is perfectly valid, in the case where the only errors that occur are that some 0-valued bits change to 1. Therefore, if all the errors that occur on a specific codeword all occur in the same direction, these errors will be detected. For the next code word being transmitted (for instance), the errors can go in the opposite direction, and they will still be detected, as long as they all go in the same direction as each other.

</p><p>Unidirectional errors are common in certain situations. For instance, in <a href="Flash_memory" title="Flash memory">flash memory</a>, bits can more easily be programmed to a 0 than can be reset to a 1.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJ._M._Berger1961" class="citation journal cs1">J. M. Berger (March 1961). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2861%2980037-5">"A note on an error detection code for asymmetric channels"</a>. <i>Information and Control</i>. <b>4</b> (1): <span class="nowrap">68–</span>73. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2861%2980037-5">10.1016/S0019-9958(61)80037-5</a></span>.</cite></li>

<li>Subhasish Mitra and Edward J. McCluskey, "<a rel="nofollow" class="external text" href="https://web.archive.org/web/20170705061209/http://crc.stanford.edu/crc_papers/mitraitc002.pdf">Which concurrent error detection scheme to choose?</a>", Center for Reliable Computing, Stanford University, 2000.</li>

<li><cite id="CITEREFTom_Verhoeff1988" class="citation journal cs1">Tom Verhoeff (March 1988). <a rel="nofollow" class="external text" href="http://alexandria.tue.nl/extra1/wskrap/publichtml/8837761.pdf">"Delay-insensitive codes — an overview] by"</a> <span class="cs1-format">(PDF)</span>. <i>Distributed Computing</i>. <b>3</b> (1): <span class="nowrap">1–</span>8. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01788562">10.1007/BF01788562</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8568354">8568354</a>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2022-11-10" href="https://en.wikipedia.org/wiki/?title=Berger_code&oldid=1121111958">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>